// 两数之和II - 输入有序数组
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        int left = 0, right = numbers.size() - 1;

        while(left < right)
        {
            int sum = numbers[left] + numbers[right];

            if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
            else if(sum == target)
            {
                return {left + 1, right + 1};
            }
        }

        return {-1, -1};
    }
};


// 两数之和 - 比较特殊（返回的是索引，还是无序数组）
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        // 建立 val->index 的映射
        unordered_map<int, int> map;

        // for(int j = 0; j < nums.size(); j++)
        // {
        //     map[nums[j]] = j;
        // }


        // for(int i = 0; i < nums.size(); i++)
        // {
        //     // map[nums[i]] = i;

        //     //查表，看是否有 target-nums[i] 相等的值
        //     int need = target - nums[i];

        //     if(map.count(need))
        //     {
        //         // return {i, map[need]};
        //         return {map[need], i};
        //     }

        //     // 记录 val->index 的映射
        //     map[nums[i]] = i;
        // }    

        for(int i = 0; i < nums.size(); i++)
        {
            // 查表，看是否有 target-nums[i] 相等的值
            int need = target - nums[i];

            if(map.count(need))
            {
                return {map[need], i};
            }

            // 记录 val->index 的映射
            map[nums[i]] = i;
        }

        return {-1, -1};

        return {-1, -1};
    }
};


// 三数之和
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        int left = 0, right = nums.size() - 1;

        vector<vector<int>> res; // 用于记录结果

        // 遍历每一个数字，判断它的二元组是否符合条件
        for(int i = 0; i < nums.size(); i++)
        {
            vector<vector<int>> twoGroups = twoSum(nums, i+1, 0-nums[i]);

            // 如果存在二元组，再加上当前数字就是三元组
            for(vector<int>& threeGroup : twoGroups)
            {
                threeGroup.push_back(nums[i]);
                res.push_back(threeGroup);
            }

            // 防止第一个元素重复
            while(i < nums.size() - 1 && nums[i] == nums[i+1]) i++;
        }

        return res;
    }

    vector<vector<int>> twoSum(vector<int>& nums, int start, int target)
    {
        int left = start, right = nums.size() - 1;

        vector<vector<int>> res;

        while(left < right)
        {
            int sum = nums[left] + nums[right];
            int leftNum = nums[left], rightNum = nums[right];

            if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
            else if(sum == target)
            {
                res.push_back({nums[left], nums[right]});

                while(left < right && nums[left] == leftNum)
                    left++;
                while(left < right && nums[right] == rightNum)
                    right--;
            }
        }

        return res;
    }

};


// nSum算法框架：
// 使用这个函数之前一定要给数组先排序
// n 填写想求的是几数之和，start 从哪个索引开始计算（一般填0）
// target 填想凑出的目标和
vector<vector<int>> nSumTarget(vector<int>& nums, int n, int start, long target)
{
	int sz = nums.size();
	vector<vector<int>> res;

	// 至少是 2nSum，且数组大小不应该小于 n
	if(n < 2 || sz < n) return res;
	
	// 2nSum 是base case
	if(n == 2)
	{
		// 双指针的那一套操作
		int left = start, right = nums.size() - 1;

		while(left < right)
		{
			int sum = nums[left] + nums[right];
			
			int leftNum = nums[left], rightNum = nums[right];

			if(sum < target)
			{
				left++;
			}
			else if(sum > target)
			{
				right--;
			}
			else if(sum == target)
			{
				res.push_back({nums[left], nums[right]});
				while(left < right && nums[left] == leftNum)
					left++;
				while(lefe < right && nums[right] == rightNum)
					right--;
			}
		}
	}
	else 
	{
		// n > 2是，递归计算（n-1）Sum的结果
		for(int i = start; i < sz; i++)
		{
			vector<vector<int>> sub = nSumTarget(nums,n-1,i+1,target-nums[i]);
			for(vector<int>& arr : sub)
			{
				// (n-1)Sum 加上 nums[i] 就是nSum
				arr.push_back(nums[i]);
				res.push_back(arr);
			}
			while(i < sz-1 && nums[i] == nums[i+1]) i++
		}
	}

	return res;
}


// 四数之和
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(), nums.end());

        return nSumTarget(nums, 4, 0, target);
    }

    vector<vector<int>> nSumTarget(vector<int>& nums, int n/*几数之和*/, int start/*从哪个索引开始*/, long target/*想凑出的目标值*/)
    {
        int sz = nums.size();


        vector<vector<int>> res; // 用于记录结果

        if(n < 2 || sz < n) return res;

        if(n == 2)
        {
            int left = start, right = sz - 1;

            while(left < right)
            {
                int sum = nums[left] + nums[right];
                int leftNum = nums[left], rightNum = nums[right];

                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {   
                    right--;
                }
                else if(sum == target)
                {
                    res.push_back({leftNum, rightNum});

                    while(left < right && nums[left] == leftNum)
                        left++;
                    
                    while(left < right && nums[right] == rightNum)
                        right--;
                }
            }

        }
        else
        {
            // 当n>2时，递归计算(n-1)Sum的结果
            for(int i = start; i < sz; i++)
            {
                vector<vector<int>> ret=nSumTarget(nums,n-1,i+1,target-nums[i]);

                for(vector<int>& v1 : ret)
                {
                    v1.push_back(nums[i]);
                    res.push_back(v1);
                }

                while(i < sz - 1 && nums[i] == nums[i+1]) i++;
            }
        }
        return res;

    }
};


// 四数之和
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(), nums.end());

        return nSumTarget(nums, 4, 0, target);
    }

    vector<vector<int>> nSumTarget(vector<int>& nums, int n, int start, long target)
    {
        int sz = nums.size();

        vector<vector<int>> res; // 用于记录结果

        if(n < 2 || sz < n) return res;

        if(n == 2)
        {
            int left = start, right = nums.size() - 1;

            while(left < right)
            {
                int sum = nums[left] + nums[right];
                int leftNum = nums[left], rightNum = nums[right];

                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
                else if(sum == target)
                {
                    res.push_back({leftNum, rightNum});

                    while(left < right && nums[left] == leftNum) left++;
                    while(left < right && nums[right] == rightNum) right--;
                }
            }
        }
        else 
        {
            // n>2时，递归计算(n-1)Sum
            for(int i = start; i < sz; i++)
            {
                vector<vector<int>> arr = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                for(vector<int>& v1 : arr)
                {
                    v1.push_back(nums[i]);
                    res.push_back(v1);
                }

                while(i < sz - 1 && nums[i] == nums[i + 1]) i++;
            }
        }

        return res;
    }
};


// 三数之和
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        return nSumTarget(nums, 3, 0, 0);
    }

    vector<vector<int>> nSumTarget(vector<int>& nums, int n, int start, int target)
    {
        int sz = nums.size();

        vector<vector<int>> res; // 用于记录结果

        if(n < 2 || sz < n) return res;

        if(n == 2)
        {
            int left = start, right = sz - 1;

            while(left < right)
            {
                int sum = nums[left] + nums[right];
                int leftNum = nums[left], rightNum = nums[right];

                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
                else if(sum == target)
                {
                    res.push_back({leftNum, rightNum});

                    while(left < right && nums[left] == leftNum) left++;
                    while(left < right && nums[right] == rightNum) right--;
                }
            }
        }
        else
        {
            // 递归求解(n-1)Sum
            for(int i = start; i < sz; i++)
            {
                vector<vector<int>> arr = nSumTarget(nums, n - 1, i + 1, target - nums[i]);

                for(vector<int>& v1 : arr)
                {
                    v1.push_back(nums[i]);
                    res.push_back(v1);
                }

                // 防止第一个元素重复
                while(i < sz - 1 && nums[i] == nums[i+1]) i++;
            }
        }

        return res;
    }
};


// 四数之和
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(), nums.end());

        return nSum(nums, 4, 0, target);
    }

    vector<vector<int>> nSum(vector<int>& nums, int n, int start, long target)
    {
        int sz = nums.size();
        vector<vector<int>> ret;

        if(n < 2 || n > sz)
        {
            return {};
        }

        int left = start, right = sz - 1;

        if(n == 2)
        {
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                int leftNum = nums[left], rightNum = nums[right];

                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
                else if(sum == target)
                {
                    ret.push_back({leftNum, rightNum});
                    while(left < right && nums[left] == leftNum) left++;
                    while(left < right && nums[right] == rightNum) right--;
                }
            }
        }
        else
        {
            for(int i = start; i < sz; i++)
            {
                vector<vector<int>> arr = nSum(nums,n-1,i+1,target-nums[i]);

                for(vector<int>& v : arr)
                {
                    v.push_back(nums[i]);
                    ret.push_back(v);
                }

                // 防止第一个元素重复
                while(i < sz - 1 && nums[i] == nums[i + 1]) i++;
            }

            
        }

        return ret;
    }
};



class NumArray {

private:
    vector<int> preNums;

public:
    NumArray(vector<int>& nums) 
    {
        preNums.resize(nums.size() + 1);

        for(int i = 1; i <= nums.size(); i++)
        {
            preNums[i] = preNums[i - 1] + nums[i - 1];
        }
    }
    
    int sumRange(int left, int right) 
    {
        return preNums[right + 1] - preNums[left];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        // 建立值到索引的映射
        unordered_map<int, int> valToIndedx;

        for(int i = 0; i < nums.size(); i++)
        {
            int need = target - nums[i];

            if(valToIndedx.count(need))
            {
                return {valToIndedx[need], i};
            }

            valToIndedx[nums[i]] = i;
        }    

        return {-1, -1};
    }
};


class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        int left = 0, right = numbers.size() - 1;

        while(left < right)
        {
            int sum = numbers[left] + numbers[right];

            if(sum < target)
                left++;
            else if(sum > target)
                right--;
            else if(sum == target)
                return {left + 1, right + 1};
        }

        return {-1, -1};
    }
};


vector<vector<int>> threeSum(vector<int>& nums)
{
	sort(nums.begin(), nums.end());
	return nSum(nums, 3, 0, 0);
}

vector<vector<int>> nSum(vector<int>& nums, int n, int start, int target)
{
	vector<vector<int>> res;

	int sz = nums.size();

	if(n < 2 || n > sz)
		return res;
	
	if(n == 2)
	{
		int left = start, right = sz - 1;
		while(left < right)
		{
			int sum = nums[left] + nums[right];

			int leftNum = nums[left], rightNum = nums[right];

			if(sum < target)
				left++;
			else if(sum > target)
				right--;
			else if(sum == target)
			{
				res.push_back({leftNum, rightNum});
				while(left < right && nums[left] == leftNum) left++;
				while(left < right && nums[right] == rightNum) right--;
		}
	}
	else
	{
		// 递归计算(n-1)Sum的值
		for(int i = start; i < sz; i++)
		{
			vector<vector<int>> arr = nSum(nums, n - 1, i + 1, target - nums[i]);

			for(vector<int>& v : arr)
			{
				v.push_back(nums[i]);
				res.push_back(v);
			}
			
		// 防止第一个元素重复
		while(i < sz - 1 && nums[i] == nums[i + 1]) i++;
		}
	}
	return res;
}


class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        return nSum(nums, 3, 0, 0);
    }

    vector<vector<int>> nSum(vector<int>& nums, int n, int start, int target)
    {
        vector<vector<int>> res;

        int sz = nums.size();
        if(n < 2 || n > sz)
            return res;

        if(n == 2)
        {
            int left = start, right = sz - 1;

            while(left < right)
            {
                int leftNum = nums[left], rightNum = nums[right];
                int sum = leftNum + rightNum;
                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
                else if(sum == target)
                {
                    res.push_back({leftNum, rightNum});
                    while(left < right && nums[left] == leftNum) left++;
                    while(left < right && nums[right] == rightNum) right--;
                }
            }
        }
        else
        {
            // 递归求解(n-1)Sum
            for(int i = start; i < sz; i++)
            {
                vector<vector<int>> ret = nSum(nums, n-1, i+1, target-nums[i]);
                // 再加上nums[i]即可满足条件
                for(vector<int>& v : ret)
                {
                    v.push_back(nums[i]);
                    res.push_back(v);
                }

                // 防止第一个元素重复
                while(i < sz - 1 && nums[i] == nums[i + 1]) i++;
            }
        }

        return res;

    }
};


class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        return nSum(nums, 3, 0, 0);
    }

    vector<vector<int>> nSum(vector<int>& nums, int n, int start, int target)
    {
        vector<vector<int>> res;

        int sz = nums.size();

        if(n < 2 || n > sz)
            return res;

        if(n == 2)
        {
            int left = start, right = sz - 1;

            while(left < right)
            {
                int leftNum = nums[left], rightNum = nums[right];
                int sum = leftNum + rightNum;

                if(sum < target)
                {
                    while(left < right && leftNum == nums[left]) left++;
                }
                else if(sum > target)
                {
                    while(left < right && rightNum == nums[right]) right--;
                }
                else if(sum == target)
                {
                    res.push_back({leftNum, rightNum});
                    while(left < right && leftNum == nums[left]) left++;
                    while(left < right && rightNum == nums[right]) right--;
                }
            }
        }
        else
        {
            // 递归计算(n-1)Sum的值
            for(int i = start; i < sz; i++)
            {
                vector<vector<int>> ret = nSum(nums,n-1,i+1,target-nums[i]);
                //(n-1)Sum加上nums[i]就是nSum
                for(vector<int>& arr : ret)
                {
                    arr.push_back(nums[i]);
                    res.push_back(arr);
                }

                // 防止第一个元素重复
                while(i < sz - 1 && nums[i] == nums[i + 1]) i++;
            }
        }
        return res;
    }
};


class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(), nums.end());

        return nSum(nums, 4, 0, target);
    }

    vector<vector<int>> nSum(vector<int>& nums, int n, int start, long target)
    {
        vector<vector<int>> res;

        int sz = nums.size();

        if(n < 2 || n > sz) return res;

        if(n == 2)
        {
            int left = start, right = sz - 1;

            while(left < right)
            {
                int leftNum = nums[left], rightNum = nums[right];
                int sum = leftNum + rightNum;

                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
                else if(sum == target)
                {
                    res.push_back({leftNum, rightNum});
                    while(left < right && leftNum == nums[left]) left++;
                    while(left < right && rightNum == nums[right]) right--;
                }
            }
        }
        else
        {
            for(int i = start; i < sz; i++)
            {
                vector<vector<int>> ret = nSum(nums,n-1,i+1,target-nums[i]);
                for(vector<int>& arr : ret)
                {
                    arr.push_back(nums[i]);
                    res.push_back(arr);
                }

                // 防止第一个元素重复
                while(i < sz - 1 && nums[i] == nums[i + 1]) i++;
            }
        }

        return res;
    }
};


class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(), nums.end());

        return nSum(nums, 4, 0, target);
    }

    vector<vector<int>> nSum(vector<int>& nums, int n, int start, long target)
    {
        vector<vector<int>> res;

        int sz = nums.size();

        if(n < 2 || sz < n)
            return res;

        if(n == 2)
        {
            int left = start, right = sz - 1;

            while(left < right)
            {
                int leftNum = nums[left], rightNum = nums[right];
                int sum = leftNum + rightNum;

                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
                else if(sum == target)
                {
                    res.push_back({leftNum, rightNum});

                    while(left < right && nums[left] == leftNum)
                        left++;
                    while(left < right && nums[right] == rightNum)
                        right--;
                }
            }
        }
        else
        {
            for(int i = start; i < sz; i++)
            {
                vector<vector<int>> groups = nSum(nums, n - 1, i + 1, target - nums[i]);

                for(auto& group : groups)
                {
                    group.push_back(nums[i]);
                    res.push_back(group);
                }

                while(i < sz - 1 && nums[i + 1] == nums[i])
                    i++;
            }
        }   

        return res;
    }
};



